// 执行所有任务的最少初始电量
// 每一个任务有两个参数，需要耗费的电量、至少多少电量才能开始这个任务
// 返回手机至少需要多少的初始电量，才能执行完所有的任务
// 来自真实大厂笔试，没有在线测试，对数器验证

#include <bits/stdc++.h>

using namespace std;

int f1(vector<vector<int>>& jobs, int n, int i)
{
    if(i == n)
    {
        int ans = 0;
        // job[0] : 耗费电量
        // job[1] : 至少电量
        for(auto& job : jobs)
        {
            ans = max(job[0] + ans, job[1]);
        }
        return ans;
    }
    else
    {
        int ans = INT_MAX;
        for(int j = i; j < n; ++j)
        {
            swap(jobs[i], jobs[j]);
            ans = min(ans, f1(jobs, n, i + 1));
            swap(jobs[i], jobs[j]);
        }
        return ans;
    }
}

// 暴力递归
// 为了验证
// 时间复杂度O(n!)
// 得到所有排列
// 其中一定有返还电量最小的排列
int atLeast1(vector<vector<int>>& jobs)
{
    return f1(jobs, jobs.size(), 0);
}

// 正式方法
// 贪心
// 时间复杂度O(n * logn)
int atLeast2(vector<vector<int>>& jobs)
{
    // jobs[i][0] : 耗费电量
    // jobs[i][1] : 至少电量
    // 至少电量一样，耗费电量越大，越先倒推
    // 8 10 ==> 18   6 10 ==> 16
    // 6 10          8 10
    // 耗费电量一样，至少电量越小，越先倒推
    // 10 25 ==> 32  10 22 ==> 35
    // 10 22         10 25
    // 结论：消耗电量 - 至少电量，越大的任务，越先倒推
    sort(jobs.begin(), jobs.end(), [](auto& a, auto& b){
        return (a[0] - a[1]) > (b[0] - b[1]);
    });
    int ans = 0;
    for(auto& job : jobs)
    {
        ans = max(ans + job[0], job[1]);
    }
    return ans;
}

// 为了验证
vector<vector<int>> randomJobs(int n, int v)
{
    vector<vector<int>> ans(n, vector<int>(2));
    for(int i = 0; i < n; ++i)
    {
        ans[i][0] = rand() % v + 1; // 耗费电量
        ans[i][1] = rand() % v + 1; // 至少电量
    }
    return ans;
}

// 为了验证
int main()
{
    srand(time(nullptr));
    int N = 10;
    int V = 20;
    int testTimes = 2000;
    cout << "测试开始" << endl;
    for(int i = 1; i <= testTimes; ++i)
    {
        int n = rand() % N + 1;
        vector<vector<int>> jobs = randomJobs(n, V);
        int ans1 = atLeast1(jobs);
        int ans2 = atLeast2(jobs);
        if(ans1 != ans2) cout << "出错了！" << endl;
        if(i % 100 == 0) cout << "(测试到第" << i << "组)" << endl;
    }
    cout << "测试结束" << endl;

    return 0;
}